#pragma once

#ifndef List_h
#define List_h

#ifndef ALIGNED
#define ALIGNED(v,a)    (((v) + ((a)-1)) & ~((a) - 1))
#endif

#include <stdlib.h>
#include <malloc.h>
#include <new>

#define LIST_SIZE_INCREMENT     8

namespace fusion
{
	template <typename T> const T& max (const T& a, const T& b)
	{
		return a > b ? a : b;
	}
    template <typename T>
    class Allocator
    {
    public:
        template <typename U>
        Allocator(const U& _t) : t(_t)
        {
        }
        template <class _Ty>
        void* __cdecl operator new(size_t, _Ty* p)
        {
            return p;
        }
        template <class _Ty>
        void __cdecl operator delete(void*, _Ty*)
        {
        }
        T t;
    };

    template <class T>
    class DefaultComparator
    {
    public:
        static int Compare(const T& t1, const T& t2)
        {
            if (t1 == t2)
            {
                return 0;
            }
            else if (t1 < t2)
            {
                return -1;
            }
            return 1;
        }
    };

    namespace ResizePolicy
    {
        enum Enum
        {
            Normal,
            ExactFit
        };
    }

    template < class T >
    class List
    {
    private:
        typedef fusion::Allocator<T> Allocator;

    public:
        typedef size_t size_type;
        typedef T data_type;

        // Iterator support
        typedef T* iterator;
        typedef const T* const_iterator;

        inline iterator begin() { return m_pData; }
        inline iterator end() { return m_pData + m_nSize; }
        inline const_iterator begin() const { return m_pData; }
        inline const_iterator end() const { return m_pData + m_nSize; }

        List()
            : m_pData(NULL)
            , m_nSize(0)
            , m_nMemorySize(0)
        {
        }

        List(const List<T>& other)
            : m_pData(NULL)
            , m_nSize(0)
            , m_nMemorySize(0)
        {
            Copy(other);
        }

        template <typename U>
        List(const List<U>& other)
            : m_pData(NULL)
            , m_nSize(0)
            , m_nMemorySize(0)
        {
            Copy(other);
        }

        virtual ~List()
        {
            clear();
        }

        List<T>& operator=(const List<T>& rhs)
        {
            Copy(rhs.m_pData, rhs.m_nSize);
            return *this;
        }

        template <typename U>
        void Copy(const U* data, size_type count)
        {
            for (size_type i = 0; i < size(); ++i)
            {
                m_pData[i].~T();
            }
            m_nSize = 0;

            if (ResizeMemory(count, ResizePolicy::Normal))
            {
                m_nSize = count;
                for (size_type i = 0; i < count; ++i)
                {
                    new (m_pData + i) Allocator(data[i]);
                }
            }
        }

        template <typename U>
        void Copy(const List<U>& other)
        {
            Copy(other.begin(), other.size());
        }

        void Trim()
        {
            ResizeMemory(size(), ResizePolicy::ExactFit);
        }

        template <typename U>
        bool push_back(const U& value)
        {
            if (!ResizeMemory(max(m_nSize + 1, m_nMemorySize)))
            {
                return false;
            }

            new (m_pData + m_nSize) Allocator(value);
            // $TODO: Use Atomic::Increment
            m_nSize++;
            return true;
        }

        template <typename U>
        bool insert(size_type nIndex, const U& value)
        {
            if (!ResizeMemory(max(m_nSize + 1, m_nMemorySize)))
            {
                return false;
            }

            if (nIndex > m_nSize)
            {
                nIndex = m_nSize;
            }

            memmove(m_pData + nIndex + 1, m_pData + nIndex, (m_nSize - nIndex) * sizeof(T));

            // $TODO: Use Atomic::Increment
            m_nSize++;
            new(m_pData + nIndex) Allocator(value);

            return true;
        }

        template <typename U>
        iterator insert(iterator item, const U& value)
        {
            size_type index = item - m_pData;
            if (index <= m_nSize && insert(index, value))
            {
                return m_pData + index;
            }

            throw_exception();
            return NULL;
        }

        template <typename U>
        bool insertFill(size_type nIndex, const U& value, size_type fillCount)
        {
            if (!ResizeMemory(m_nSize + fillCount))
            {
                return false;
            }

            if (nIndex > m_nSize)
            {
                nIndex = m_nSize;
            }

            memmove(m_pData + nIndex + fillCount, m_pData + nIndex, (m_nSize - nIndex) * sizeof(T));

            m_nSize += fillCount;

            for (size_type i = 0; i < fillCount; ++i)
            {
                new(&m_pData[nIndex + i]) Allocator(value);
            }

            return true;
        }

        template <typename U>
        iterator insertFill(iterator item, const U& value, size_type fillCount)
        {
            size_type index = item - m_pData;
            if (index <= m_nSize && insert(index, value, fillCount))
            {
                return m_pData + index;
            }

            throw_exception();
            return NULL;
        }

        void pop_back(size_type count = 1)
        {
            erase(m_nSize - count, count);
        }

        iterator erase(size_type nIndex, size_type count = 1)
        {
            for (size_type i = nIndex; i < nIndex + count; ++i)
            {
                m_pData[i].~T();
            }

            if (nIndex + count < m_nSize)
            {
                memmove(m_pData + nIndex, m_pData + nIndex + count, (m_nSize - nIndex - count) * sizeof(T));
            }
            // $TODO: Use Atomic::Decrement
            m_nSize -= count;
            ResizeMemory(m_nSize);
            return m_pData + nIndex;
        }

        iterator erase(iterator item)
        {
            size_type index = item - m_pData;
            if (index < m_nSize)
            {
                return erase(index);
            }
            return end();
        }

        size_type size() const
        {
            return m_nSize;
        }

        size_t itemSize() const
        {
            return sizeof(T);
        }

        void resize(size_type size, ResizePolicy::Enum policy = ResizePolicy::Normal)
        {
            resize(size, T(), policy);
        }

        void resize(size_type size, const T& fillValue, ResizePolicy::Enum policy = ResizePolicy::Normal)
        {
            while (size < m_nSize)
            {
                m_pData[--m_nSize].~T();
            }

            if (ResizeMemory(size, policy))
            {
                while (m_nSize < size)
                {
                    new (m_pData + m_nSize) Allocator(fillValue);
                    m_nSize++;
                }
            }
        }

        bool reserve(size_type size, ResizePolicy::Enum policy = ResizePolicy::Normal)
        {
            return ResizeMemory(max(size, m_nMemorySize), policy);
        }

        bool grow(size_type size, ResizePolicy::Enum policy = ResizePolicy::Normal)
        {
            // This method should only be called when you are going to fill in the new
            // objects at the end of the list before attempting to read them.

            // It avoids the cost of the fillValue in resize.

            bool success = true;
            if (m_nMemorySize - m_nSize < size)
            {
                success = reserve(m_nSize + size, policy);
            }

            if (success)
            {
                m_nSize += size;
            }
            return success;
        }

        T& front()
        {
            return m_pData[0];
        }

        const T& front() const
        {
            return m_pData[0];
        }

        T& back()
        {
            return m_pData[m_nSize - 1];
        }

        const T& back() const
        {
            return m_pData[m_nSize - 1];
        }

        T& operator[](size_type value)
        {
            return m_pData[value];
        }

        const T& operator[](size_type value) const
        {
            return m_pData[value];
        }

        T& at(size_type value)
        {
            return m_pData[value];
        }

        const T& at(size_type value) const
        {
            return m_pData[value];
        }

        T& at(iterator item)
        {
            return *item;
        }

        const T& at(const_iterator item) const
        {
            return *item;
        }

        void clear()
        {
            if (m_pData != NULL)
            {
                for (size_type i = 0; i < size(); ++i)
                {
                    m_pData[i].~T();
                }
                FreeMemory();
            }

            m_nSize = 0;
        }

        template < class TCompare >
        void sort()
        {
            qsort(m_pData, m_nSize, sizeof(T), SortProxy<TCompare>);
        }

        void sort() { sort< DefaultComparator<T> >(); }

        void swap(List& rhs)
        {
            fusion::swap(m_pData, rhs.m_pData);
            fusion::swap(m_nSize, rhs.m_nSize);
            fusion::swap(m_nMemorySize, rhs.m_nMemorySize);
        }

        void swap(size_type firstIndex, size_type secondIndex)
        {
            T value = m_pData[firstIndex];
            m_pData[firstIndex] = m_pData[secondIndex];
            m_pData[secondIndex] = value;
        }

        template <typename U>
        inline iterator find_first(const U& key, size_type beginIndex = 0) { return find_first(key, beginIndex, size()); }

        template <typename U>
        iterator find_first(const U& key, size_type beginIndex, size_type endIndex)
        {
            for (size_type i = beginIndex; i < endIndex; ++i)
                if (m_pData[i] == key)
                {
                    return m_pData + i;
                }
            return end();
        }

        template <typename U>
        inline const_iterator find_first(const U& key, size_type beginIndex = 0) const { return find_first(key, beginIndex, size()); }

        template <typename U>
        const_iterator find_first(const U& key, size_type beginIndex, size_type endIndex) const
        {
            for (size_type i = beginIndex; i < endIndex; ++i)
                if (m_pData[i] == key)
                {
                    return m_pData + i;
                }
            return end();
        }

        template <typename U, class TCompare>
        inline const_iterator binarySearch(const U& key) const // Binary search (must be sorted!)
        {
            const_iterator base = m_pData;
            int lim;
            const_iterator p;

            for (lim = static_cast<int>(m_nSize); lim != 0; lim >>= 1)
            {
                p = base + (lim >> 1);
                if (TCompare::IsKeyGt(*p, key))     /* key > p: move right */
                {
                    base = p + 1;
                    lim--;
                }
                else if (TCompare::IsKeyEqual(*p, key))
                {
                    return (p);
                } /* else move left */
            }

            return end();
        }

        template <typename U>
        const_iterator binarySearch(const U& key) const { return binarySearch< U, DefaultComparator<T> >(key); }

        template <typename U>
        bool operator==(const List<U>& that) const
        {
            if (size() != that.size()) { return false; }
            for (size_type i = 0; i < size(); ++i)
            {
                if ((*this)[i] != that[i]) { return false; }
            }
            return true;
        }

        template <typename U>
        bool operator!=(const List<U>& that) const
        {
            return !((*this) == that);
        }
        // This tells the marshalling code to call our custom marshalling methods.
        static const bool use_direct_marshalling = false;

    protected:
        template <class TCompare>
        static int SortProxy(const void* item1, const void* item2)
        {
            return TCompare::Compare(*(const T*)item1, *(const T*)item2);
        }

        virtual bool ResizeMemory(const size_type nSize, ResizePolicy::Enum policy = ResizePolicy::Normal)
        {
            size_type nMemorySize = nSize;

            if (policy == ResizePolicy::Normal)
            {
                if (m_nMemorySize < nSize)
                {
                    // Attempt to grow the memory by 50%
                    nMemorySize = max(m_nMemorySize + (m_nMemorySize >> 1), max(nSize, static_cast<size_type>(8)));
                }
                else
                {
                    // There is already enough memory to hold the new items
                    return true;
                }
            }
            else if (policy == ResizePolicy::ExactFit)
            {
                if (nMemorySize == m_nMemorySize)
                {
                    return true;
                }
            }

            // Allocate new storage
            T* pData = reinterpret_cast<T*>(realloc(m_pData, nMemorySize * sizeof(T)));

            if (nSize == 0 || pData != NULL)
            {
                m_pData = pData;
                m_nMemorySize = nMemorySize;
                return true;
            }

            return false;
        }

        virtual void FreeMemory()
        {
            if (m_pData) { free(m_pData); }
            m_pData = NULL;
            m_nMemorySize  = 0;
        }

        static void throw_exception()
        {
            
        }

        T*              m_pData;
        size_type       m_nSize;
        size_type       m_nMemorySize;
    };

    // $TODO: This is intended for small number of simple types or pointers only. Optimization will be done later.

    template <class TKey, class TValue>
    class Map
    {
    public:
        typedef int Index;
        static const Index BAD_INDEX;
        typedef Index SizeType;
        struct Element
        {
            TKey m_Key;
            TValue m_Value;

            template <typename UKey>
            explicit Element(const UKey& key)
                : m_Key(key), m_Value()
            {
            }

            template <typename UKey, typename UValue>
            Element(const UKey& key, const UValue& value)
                : m_Key(key), m_Value(value)
            {
            }
        };

        // Iterator support
        // This iterator allows iterating either keys or values.
        template<class T, size_t Offset>
        class PairIterator
        {
            friend class PairIterator<const T, sizeof(Element)>;
        public:
            PairIterator(T* begin)
                : m_Pos(begin)
            {
            }

            PairIterator(const PairIterator& that)
                : m_Pos(that.m_Pos)
            {}

            template<class OtherT>
            PairIterator(const PairIterator<OtherT, sizeof(Element)>& that)
                : m_Pos(that.m_Pos)
            {}

            PairIterator& operator++() // pre increment
            {
                byte* p = (byte*)m_Pos;
                m_Pos = (T*)(p + Offset);
                return *this;
            }

            PairIterator operator++(int) // post increment
            {
                PairIterator tmp(*this);
                ++(*this);
                return tmp;
            }

            bool operator==(const PairIterator& rhs) const
            {
                return m_Pos == rhs.m_Pos;
            }

            bool operator!=(const PairIterator& rhs) const
            {
                return m_Pos != rhs.m_Pos;
            }

            const T& operator*() const
            {
                return *m_Pos;
            }

            const TKey& operator->() const
            {
                return *m_Pos;
            }

        private:
            T* m_Pos;
        };

        typedef PairIterator<TKey, sizeof(Element)> key_iterator;
        typedef PairIterator<TKey const, sizeof(Element)> const_key_iterator;

        typedef PairIterator<TValue, sizeof(Element)> value_iterator;
        typedef PairIterator<TValue const, sizeof(Element)> const_value_iterator;

        inline key_iterator begin_keys()
        {
            return key_iterator(&m_pData[0].m_Key);
        }

        inline const_key_iterator begin_keys() const
        {
            return const_key_iterator(&m_pData[0].m_Key);
        }

        inline key_iterator end_keys()
        {
            return key_iterator(&m_pData[m_nSize].m_Key);
        }

        inline const_key_iterator end_keys() const
        {
            return const_key_iterator(&m_pData[m_nSize].m_Key);
        }

        inline value_iterator begin_values()
        {
            return value_iterator(&m_pData[0].m_Value);
        }

        inline const_value_iterator begin_values() const
        {
            return const_value_iterator(&m_pData[0].m_Value);
        }

        inline value_iterator end_values()
        {
            return value_iterator(&m_pData[m_nSize].m_Value);
        }

        inline const_value_iterator end_values() const
        {
            return const_value_iterator(&m_pData[m_nSize].m_Value);
        }

        Map() : m_pData(NULL), m_nSize(0), m_nMaxSize(0)
        {
        }

        Map(const Map<TKey, TValue>& other) : m_pData(NULL), m_nSize(0), m_nMaxSize(0)
        {
            Reserve(other.Size());

            for (int i = 0; i < other.Size(); ++i)
            {
                Add(other.GetKeyAt(i), other.GetValueAt(i));
            }
        }

        ~Map()
        {
            RemoveAll();
        }

        template <typename UKey, typename UValue>
        Index Add(const UKey& key, const UValue& value)
        {
            if (!Resize(m_nSize + 1))
            {
                return BAD_INDEX;
            }

            // $TODO: Use Atomic::Increment
            Set(m_nSize, key, value);
            return m_nSize++;
        }

        template <typename UKey, typename UValue>
        Index SetAt(const UKey& key, const UValue& value)
        {
            Index index = FindKey(key);
            if (index == BAD_INDEX)
            {
                return Add(key, value);
            }

            m_pData[index].~Element();

            Set(index, key, value);
            return index;
        }

        template <typename UKey>
        const TValue& operator[](const UKey& key) const
        {
            Index index = FindKey(key);
            if (index == BAD_INDEX)
            {
                throw_exception();
            }
            return GetValueAt(index);
        }

        Map<TKey, TValue>& operator =(const Map<TKey, TValue>& other)
        {
            RemoveAll();

            Reserve(other.Size());

            for (int i = 0; i < other.Size(); ++i)
            {
                Add(other.GetKeyAt(i), other.GetValueAt(i));
            }

            return *this;
        }

        template <typename UKey>
        TValue& operator[](const UKey& key)
        {
            Index index = FindKey(key);
            if (index == BAD_INDEX)
            {
                if (!Resize(m_nSize + 1))
                {
                    throw_exception();
                }

                index = m_nSize++;
                // Calling the constructor using placement new (no memory allocated)
                new(&m_pData[index]) Element(key);
            }
            return m_pData[index].m_Value;
        }

        template <typename UKey>
        bool Remove(const UKey& key)
        {
            return RemoveAt(FindKey(key));
        }

        bool RemoveAt(Index index)
        {
            if (0 > index || index >= m_nSize)
            {
                return false;
            }

            m_pData[index].~Element();

            if (index != (m_nSize - 1))
            {
                memcpy(&m_pData[index], &m_pData[index + 1], (m_nSize - index - 1) * sizeof(Element));
            }

            --m_nSize;
            return true;
        }

        void RemoveAll()
        {
            if (m_pData)
            {
                for (SizeType i = 0; i < Size(); ++i)
                {
                    m_pData[i].~Element();
                }
                free(m_pData);
                m_pData = NULL;
            }

            m_nSize = 0;
            m_nMaxSize = 0;
        }

        template <typename UKey>
        Index FindKey(const UKey& key) const
        {
            for (SizeType i = 0; i < m_nSize; ++i)
            {
                if (m_pData[i].m_Key == key)
                {
                    return i;
                }
            }
            return BAD_INDEX;
        }

        template <typename UValue>
        Index FindValue(const UValue& value) const
        {
            for (SizeType i = 0; i < m_nSize; ++i)
            {
                if (m_pData[i].m_Value == value)
                {
                    return i;
                }
            }
            return BAD_INDEX;
        }

        TKey& GetKeyAt(Index index) const
        {
            //ASSERT(0 <= index && index < m_nSize);
            if (0 > index || index >= m_nSize)
            {
                throw_exception();
            }
            return m_pData[index].m_Key;
        }

        TValue& GetValueAt(Index index) const
        {
            //ASSERT(0 <= index && index < m_nSize);
            if (0 > index || index >= m_nSize)
            {
                throw_exception();
            }
            return m_pData[index].m_Value;
        }

        SizeType Size() const
        {
            return m_nSize;
        }

        void Reserve(SizeType size)
        {
            Resize(size);
        }

    private:
        template <typename UKey, typename UValue>
        void Set(Index index, const UKey& key, const UValue& value)
        {
            // Calling the constructor using placement new (no memory allocated)
            new(&m_pData[index]) Element(key, value);
        }

        bool Resize(SizeType size)
        {
            if (size <= m_nMaxSize)
            {
                return true;
            }

            SizeType elementCount = ALIGNED(size, LIST_SIZE_INCREMENT);
            Element* p = (Element*)realloc(m_pData, elementCount * sizeof(Element));
            if (!p && elementCount != 0)
            {
                return false;
            }

            m_nMaxSize = elementCount;
            m_pData = p;

            return true;
        }

        static void throw_exception()
        {
            //ASSERT(false);
        }

    private:
        Element*    m_pData;
        SizeType    m_nSize;
        SizeType    m_nMaxSize;
    };

    template <class TKey, class TValue>
    const typename Map<TKey, TValue>::Index Map<TKey, TValue>::BAD_INDEX = -1;

    template <class T>
    inline void swap(List<T>& lhs, List<T>& rhs)
    {
        return lhs.swap(rhs);
    }
}
#endif // List_h
